package 中等.搜索.广度优先搜索;

import util.TreeNode;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

/**
 * 给定一棵二叉树的根节点 root ，请找出该二叉树中每一层的最大值。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/find-largest-value-in-each-tree-row/
 */
public class 在每个树行中找最大值_515 {

    public static void main(String[] args) {

    }

    public List<Integer> largestValues(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        if (root == null) return list;
        Deque<TreeNode> queue = new ArrayDeque<>();
        queue.addLast(root);
        while (!queue.isEmpty()) {
            int size = queue.size();
            int curMax = queue.peek().val;
            while (size-- > 0) {
                TreeNode curNode = queue.pollFirst();
                curMax = Math.max(curMax, curNode.val);
                if (curNode.right != null) queue.addLast(curNode.right);
                if (curNode.left != null) queue.addLast(curNode.left);
            }
            list.add(curMax);
        }
        return list;
    }

}
